'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-10-24 14:24:33
'''
#
# @lc app=leetcode.cn id=15 lang=python3
#
# [15] 三数之和
#

# @lc code=start
from typing import List
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        # print(nums)
        ans=[]
        for i in range(len(nums)):
            if i and nums[i]==nums[i-1]:
                continue
            k, j=len(nums)-1, i+1
            while j <k:
                if j==i+1 or nums[j]!=nums[j-1]:
                    # print(nums[i], nums[j], nums[k])
                    if nums[i]+nums[j]+nums[k]==0:
                        ans.append([nums[i], nums[j], nums[k]])
                        j+=1
                    elif nums[i]+nums[j]+nums[k]>0:
                        k-=1
                    else:
                        j+=1
                else:
                    j+=1
        return ans



# @lc code=end

